package engine;

import java.awt.Rectangle;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 
 * Representation for an n-sided polygon.
 * This class should provide all methods for collision detection,
 * as well as subdividing and optimizations.
 * 
 * @author dylan
 *
 */
public class NPolygon {
	private ArrayList<Vector> vertices;
	public ArrayList<Triangle> triangles;
	
	public NPolygon(){
		vertices = new ArrayList<Vector>();
		triangles = new ArrayList<Triangle>();
	}
	
	/*
	 * Gets the minimum bounding rectangle of the polygon
	 */
	public Rectangle2D getBoundingBox(){
		//This is ugly, I apologize
		int minX = 1000000;
		int minY = 1000000;
		int maxX = 0;
		int maxY = 0;
		for (Vector v: this.vertices){
			if (v.getX() < minX){
				minX = (int) v.getX();
			} else if (v.getX() > maxX){
				maxX = (int) v.getX();
			}
			if (v.getY() < minY){
				minY = (int) v.getY();
			} else if (v.getY() > minY){
				maxY = (int) v.getY();
			}
		}
		return new Rectangle(minX, maxX, minY, maxY);
	}
	
	/*
	 * Add a new vertex to the triangle.
	 * By default, this will be added between the last and first vertices.
	 */
	public void addVertex(Vector v){
		vertices.add(v);
	}
	
	/*
	 * Wrapper for manually inserting vertices
	 */
	public void addVertex(double x, double y){
		addVertex(new Vector(x, y));
	}
	
	/*
	 * Convert the vertices into a priority queue of Angles.
	 */
	public PriorityQueue<Angle> verticesToAngles(){
		Angle[] tempAngles = new Angle[vertices.size()];
		PriorityQueue<Angle> queue = new PriorityQueue<Angle>();
		
		for (int i = 0; i < tempAngles.length; i ++){
			Vector tempVertex = vertices.get(i);
			tempAngles[i] = new Angle(vertices.get(i > 0 ? i - 1 : tempAngles.length - 1).subtract(tempVertex),
					vertices.get(i < tempAngles.length - 1 ? i + 1 : 0).subtract(tempVertex), tempVertex);
		}
		/*
		 * Link the angles together and add them to the queue
		 */
		for (int i = 0; i < tempAngles.length; i ++){
			tempAngles[i].previousAngle = tempAngles[i > 0 ? i - 1 : tempAngles.length - 1];
			tempAngles[i].nextAngle = tempAngles[i < tempAngles.length - 1 ? i + 1 : 0];
			queue.add(tempAngles[i]);
		}
		
		return queue;
	}
	
	/*
	 * Generate all inner triangles of the polygon.
	 *  ________
	 * |\_      |
	 * |  \__   |
	 * |     \_ |
	 * |_______\|
	 * 
	 * This method relies on cross products. Given two vectors that form
	 * an angle, the cross product can be used to determine whether or not
	 * the angle is concave or convex, and how optimal its size will be.
	 */
	public void generateInnerTriangles(){
		triangles = new ArrayList<Triangle>();
		PriorityQueue<Angle> angles = verticesToAngles();
		
		/**
		 * Iterate through all angles, ignoring those with cross products below 0;
		 */
		while(!angles.isEmpty()){
			Angle angle = angles.poll();
			if (!angle.removed && angle.getCrossProduct() > 0){
				triangles.add(angle.toTriangle());
				
				/*
				 * Remove old angles
				 */
				angle.nextAngle.fastRemove();
				angle.previousAngle.fastRemove();
				
				/*
				 * Create new angles with modified and shrunk polygon.
				 */
				Angle newPrevious = new Angle(
						angle.previousAngle.v1,
						angle.nextAngle.p.subtract(angle.previousAngle.p),
						angle.previousAngle.p
						);
				Angle newNext = new Angle(
						angle.previousAngle.p.subtract(angle.nextAngle.p),
						angle.nextAngle.v2,
						angle.nextAngle.p
						);
				
				/*
				 * Link the new angles together
				 */
				newPrevious.nextAngle = newNext;
				newNext.previousAngle = newPrevious;
				
				/*
				 * Link the new angles into the polygon. Yuck!
				 */
				angle.previousAngle.previousAngle.nextAngle = newPrevious;
				angle.nextAngle.nextAngle.previousAngle = newNext;
				newPrevious.previousAngle = angle.previousAngle.previousAngle;
				newNext.nextAngle = angle.nextAngle.nextAngle;
				
				angles.add(newPrevious);
				angles.add(newNext);
			}
		}
	}
}


